package targetToOffer.elethDay;

/**
 * @author Godc
 * @description
 */
public class IsStraight {
    public static void main(String[] args) {
        IsStraightSolution s = new IsStraightSolution();
        int[] ints = {2, 1, 6, 4, 5, 8};
        s.quickSort(ints,0,ints.length-1);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
class IsStraightSolution {
    public boolean isStraight(int[] nums) {
        quickSort(nums,0,nums.length-1);
        int zeroNum = 0,diff = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if(nums[i]==0) zeroNum++;
            else{
                if(nums[i]==nums[i+1]) return false;
                if(nums[i]+1!=nums[i+1]) diff+=nums[i+1]-nums[i]-1;
            }
        }
        return zeroNum>=diff;
    }
    public void quickSort(int[] nums,int left,int right){
        if(left>=right) return;
        int base = nums[left];
        int i = left,j=right;
        while(i<j){
            while(nums[j]>=base&&i<j) j--;
            while(nums[i]<=base&&i<j) i++;
            if(i<j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[left] = nums[i];
        nums[i] = base;
        quickSort(nums,left,i-1);
        quickSort(nums,i+1,right);
    }
}
